import java.text.*;
import java.util.*;
import java.io.*;

public class ThirdOrderBackward extends Backward {

  double[][] b;

  public ThirdOrderBackward(ThirdOrderHMM hmm, Object x[]) {
    super(hmm, x);
    int L = x.length;
    b = new double[L+1][hmm.nstate];
    for (int k=1; k<hmm.nstate; k++) b[L][k] = 0;
    for (int i=L-1; i>=1; i--)
      for (int jj=0; jj<hmm.nstate; jj++) for (int j=0; j<hmm.nstate; j++) {
        double sum = Double.NEGATIVE_INFINITY;
        for (int k=0; k<hmm.nstate; k++) for (int ell=1; ell<hmm.nstate; ell++) sum = logplus(sum, hmm.loga[jj][j][k][ell] + hmm.loge[ell][hmm.getSym(x[i])] + b[i+1][ell]);
        b[i][j] = sum;
      }
  }

  double logprob() {
    ThirdOrderHMM hmm = (ThirdOrderHMM)(this.mm);
    double sum = Double.NEGATIVE_INFINITY;
    for (int ell=0; ell<hmm.nstate; ell++) sum = logplus(sum, hmm.loga[0][0][0][ell] + hmm.loge[ell][hmm.getSym(x[0])] + b[1][ell]);
    return sum;
  }

}
